package slidingwindow;

import java.util.HashMap;

public class MinWindow {

  public String minWindow(String s, String t) {
      // 创建窗口
      HashMap<Character, Integer> window = new HashMap<>();
      // 目标
      HashMap<Character, Integer> need = new HashMap<>();
      // 最小子串起点索引，长度
      int len = Integer.MAX_VALUE, start = 0;
      // 左右窗口指针
      int left = 0, right = 0;
      // 目标字符数量
      int valid = 0;
      for (char c : s.toCharArray()) {
          need.put(c, need.getOrDefault(c, 0) - 1);
      }
      while (right < s.length()) {
          // c即是将要进入窗口的字符
          char c = s.charAt(right);
          // 扩大窗口
          right++;
          // 判断该字符是否是目标字符
          if (need.containsKey(c)) {
              // 更新窗口内数据
              window.put(c, window.getOrDefault(c, 0) + 1);
              if (window.get(c).equals(need.get(c)))
                  valid++;
          }

          // 判断窗口是否需要收缩
          if (valid == need.size()) {
              // d是将要移出窗口的字符
              char d = s.charAt(left);
              // 判断是否最小子串
              if (right - left < len) {
                  start = left;
                  len = right - left;
              }
              // 缩小窗口
              left++;
              if (need.containsKey(d)) {
                  // 更新窗口内的数据
                  if (window.get(d).equals(need.get(d))) {
                      valid--;
                  }
                  window.put(c, window.get(c) - 1);
              }
          }
      }

      // 返回最小子串
      return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
  }
}
